package leetcode;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LeetCode79 {

    int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public boolean exist1(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (word.charAt(0) == board[i][j] && exist(board, word, i, j))
                    return true;
            }
        }
        return false;
    }

    //上下左右
    private boolean exist(char[][] board, String word, int row, int column) {
        Set<String> route = new HashSet<>();
        route.add(row + "-" + column);
        return false;
    }

    //------------------------------------------------------------------
    boolean result = false;

    char[][] board;

    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;
        visited = new boolean[n][m];
        this.board = board;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                helper(word, 0, i, j);
            }
        }
        return result;
    }

    private void helper(String word, int index, int x, int y) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y] || result)
            return;
        if (word.charAt(index) == board[x][y]) {
            if (index == word.length() - 1) {
                result = true;
            } else {
                visited[x][y] = true;
                helper(word, index + 1, x - 1, y);
                helper(word, index + 1, x + 1, y);
                helper(word, index + 1, x, y - 1);
                helper(word, index + 1, x, y + 1);
                visited[x][y] = false;
            }
        }
    }
}

class Point {
    private int x;
    private int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }
}
